Cos'è pumping lemma?

Il pumping lemma è un importante teorema utilizzato nella teoria dei linguaggi formali per verificare se un linguaggio è regolare o meno. Esso fornisce una condizione sufficiente per determinare se un linguaggio è regolare, basata sull'idea che i linguaggi regolari possono essere pompati (ossia man mano ingrossati) da una sequenza finita di simboli.

In sostanza, il pumping lemma afferma che se un linguaggio è regolare, allora esiste un intero positivo p che garantisce che qualsiasi stringa nel linguaggio di lunghezza maggiore o uguale a p possa essere divisa in tre sottoinsiemi (x, y, z) in modo che soddisfi alcune proprietà. In particolare, y non deve essere vuota e la concatenazione di x e yz deve essere ancora nel linguaggio.

Se queste condizioni non sono verificate, allora il linguaggio non è regolare. Il pumping lemma può quindi essere utilizzato come strumento per dimostrazioni di non regolarità di linguaggi, ma non è sufficiente per dimostrare la regolarità di un linguaggio. In questo caso, vengono utilizzati altri teoremi e metodi, come ad esempio il teorema di Kleene o l'algoritmo di determinizzazione.